package com.cyy.test_t_2_;


/**
 * 剑指Offer 面试题29
 * 数组中出现次数超过一半的数字
 * 时间限制：1秒 空间限制：32768K 
 * 题目描述：
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组
 * 中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
 */
public class t_29 {
	public static int MoreThanHalfNum_Solution(int [] array) {
		int len = array.length;
		if(len < 1) return 0;
		
		int ans = 0;
		int [] a = new int [10000];
		for(int i=0;i<len;i++){
			a[array[i]] ++;
		}
		for(int j = 0;j < a.length;j++){
			if(a[j]!= 0 && a[j] > len / 2){
				ans = j;
			} 
		}
		return ans;
    }
	
	public static void main(String []args){
		int tmp[] = {1,2,3,2,2,2,5,4,2};
		int ans = MoreThanHalfNum_Solution(tmp);
		System.out.println(ans);
	}
}
